1. Bubble Sort is the simplest of the three sorting algorithms, and also the slowest. The Bubble Sort gets its name from the way that the largest items “bubble” to the top (end). The procedure goes like this.

   1. Move the largest remaining item in the current pass to the end of the data as follows. Starting with the first two items, swap them if necessary so that the larger item is after the smaller item. Now move over one position in the list and compare to the next item. Again swap the items if necessary.

   2. Remove the largest item most recently found from the data to be searched and perform another pass with this new data at step a.

   3. Repeat steps a and b above until the number of items to be searched is one.

   To see how Bubble Sort works, let’s try an example:

   Steps Data for pass Sorted data Start pass 1: compare 4 & 1. 4 1 3 2   4 > 1 so swapped, now compare 4 & 3. 1 4 3 2   4 > 3 so swapped, now compare 4 & 2. 1 3 4 2   4 > 2 so swapped, end of pass. 1 3 2 4   Start pass 2: compare 1 & 3. 1 3 2 4 3 > 1 so no swap, now compare 3 & 2. 1 3 2 4 3 > 2 so swapped, end of pass. 1 2 3 4 Start pass 3: now compare 1 & 2. 1 2 3 4 2 > 1 so no swap. 1 2 3 4 Only one item in this pass so it is done. 1 2 3 4 Done.   1 2 3 4

   
   

2. The following program implements the Bubble Sort algorithm.

   void bubbleSort(ArrayList <Integer> list){
  for (int outer = 0; outer < list.size() - 1; outer++){
    for (int inner = 0; inner < list.size()-outer-1; inner++){
      if (list.get(inner) > list.get(inner + 1)){
        //swap list[inner] & list[inner+1]
        int temp = list.get(inner);
        list.set(inner, list.get(inner + 1));
        list.set(inner + 1, temp);
      }
    }
  }
}

3. Given a list of 6 values, the loop variables outer and inner will evaluate as follows.

When outer = inner ranges from 0 to < (6 - outer - 1) 0 0 to 4 1 0 to 3 2 0 to 2 3 0 to 1 4 0 to 0

4. When outer = 0, then the inner loop will do 5 comparisons of pairs of values. As inner ranges from 0 to 4, it does the following comparisons:

   inner if (list.get(inner) > list.get(inner + 1)) 0 if list[0] > list[1] 1 if list[1] > list[2] ... ... 4 if list[4] > list[5]

   
   

5. If (list.get(inner) > list.get(inner + 1)) is true, then the values are out of order and a swap takes place. The swap takes three lines of code and uses a temporary variable temp.

6. After the first pass (outer = 0), the largest value will be in its final resting place (and may it rest in peace). When outer = 1, the inner loop only goes from 0 to 3 because a comparison between positions 4 and 5 is unnecessary. The inner loop is shrinking.

7. Because of the presence of duplicate values, this algorithm will result in a list sorted in non-decreasing order.

8. Here is a small list of data to test your understanding of Bubble Sort. Write in the correct sequence of integers after each advance of outer. (Answers are found in Lesson A17 Handout, Sorting Answers.)

outer	57	95	88	14	25	6
1	_____	_____	_____	_____	_____	_____
2	_____	_____	_____	_____	_____	_____
3	_____	_____	_____	_____	_____	_____
4	_____	_____	_____	_____	_____	_____
5	_____	_____	_____	_____	_____	_____